package com.xcf.leetcode.hard;

/**
 * MediumNumber <br>
 * 4. 寻找两个正序数组的中位数
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
 *
 * @author xiaocf <br>
 * @version 1.0 <br>
 * @date 2020/8/5 20:06 <br>
 */
public class MediumNumber {


    /**
     * 归并
     * 时间复杂度O(m+n)
     * 空间复杂度O(m+n)
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] ints;
        if (nums1 == null) {
            ints = nums2;
        } else if (nums2 == null) {
            ints = nums1;
        } else {
            ints = new int[nums1.length + nums2.length];
            int index1 = 0;
            int index2 = 0;
            int index = 0;
            while (nums1.length > index1 || nums2.length > index2) {
                if (nums1.length <= index1) {
                    ints[index] = nums2[index2];
                    index2++;
                } else if (nums2.length <= index2) {
                    ints[index] = nums1[index1];
                    index1++;
                } else {
                    if (nums1[index1] < nums2[index2]) {
                        ints[index] = nums1[index1];
                        index1++;
                    } else {
                        ints[index] = nums2[index2];
                        index2++;
                    }
                }
                index++;
            }
        }
        if (ints.length % 2 == 1) {
            return ints[ints.length / 2];
        } else {
            return (ints[ints.length / 2] + ints[ints.length / 2 - 1]) / 2.0;
        }
    }

    /**
     * 二分查找
     * 1 2 9
     * 3 4 【5】 6 7 8
     * mn: 9 / 2 = 4
     * 分别获取中位数
     * [i=1]2、[j=2]5
     * 比较大小 2<5, 说明列表1前部分肯定在合并列表前面，排除列表1中[1,2] --> 2
     * [1 2] 9
     * 3,4,5,6 7 8
     * 分别获取中位数
     * [i=3]9、[j=2]5
     * 比较大小 9>5, 说明列表2前部分肯定在合并列表前面，排除列表2中[3,4,5] --> 2 + 2 = 4
     * [1 2] 9
     * [3 4 5] 6 7 8
     * 4 == 4 --> 【5】
     */
    public double findMedianSortedArraysV2(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) {
            if (nums2.length % 2 == 1) {
                return nums2[nums2.length / 2];
            } else {
                return (nums2[nums2.length / 2] + nums2[nums2.length / 2 - 1]) / 2.0;
            }
        }
        if (nums2 == null || nums2.length == 0) {
            if (nums1.length % 2 == 1) {
                return nums1[nums1.length / 2];
            } else {
                return (nums1[nums1.length / 2] + nums1[nums1.length / 2 - 1]) / 2.0;
            }
        }
        int mn = nums1.length + nums2.length;
        int midleIndex = mn / 2;
        int lessIndex = 0;
        while (true) {

        }
    }

    public static void main(String[] args) {
        MediumNumber number = new MediumNumber( );
        double medianSortedArrays = number.findMedianSortedArrays(new int[]{1, 3}, new int[]{2});
        System.out.println("medianSortedArrays = " + medianSortedArrays);
    }
}
